[UVA10140]Prime Distance

发表于 | 分类于 ， | | 阅读次数:

题目

题目描述

The branch of mathematics called number theory is about properties of numbers. One of the areas that has captured the interest of number theoreticians for thousands of years is the question of primality. A prime number is a number that is has no proper factors (it is only evenly divisible by 1 and itself). The first prime numbers are 2,3,5,7 but they quickly become less frequent. One of the interesting questions is how dense they are in various ranges. Adjacent primes are two numbers that are both primes, but there are no other prime numbers between the adjacent primes. For example, 2,3 are the only adjacent primes that are also adjacent numbers.
Your program is given 2 numbers: L and U (1<=L< U<=2,147,483,647), and you are to find the two adjacent primes C1 and C2 (L<=C1< C2<=U) that are closest (i.e. C2-C1 is the minimum). If there are other pairs that are the same distance apart, use the first pair. You are also to find the two adjacent primes D1 and D2 (L<=D1< D2<=U) where D1 and D2 are as distant from each other as possible (again choosing the first pair if there is a tie).
Input

给定两个整数 L,R，求闭区间 [L,R]中相邻两个质数差值最小的数对与差值最大的数对。当存在多个时，输出靠前的素数对。

输入格式

Each line of input will contain two positive integers, L and U, with L < U. The difference between L and U will not exceed 1,000,000.

输出格式

For each L and U, the output will either be the statement that there are no adjacent primes (because there are less than two primes between the two given numbers) or a line giving the two pairs of adjacent primes.

输入样例

1
2
2 17
14 17

输出样例

1
2
2,3 are closest, 7,11 are most distant.
There are no adjacent primes.

题解

部分内容来自李煜东所著《算法进阶指南》

暴力是不可能的，R的范围太大了。
但是我们发现，R-L的范围很小，有什么办法可以求出R-L之间的质数呢？
显然：

定理：如果n是一个合数， 那么n一定有一个不超过$\sqrt{n}$的素数因子
推论：任意一个合数n必定包含一个不超过$\sqrt{n}$的质因子

用质因数分解定理可以简单证明。
所以，我们只要用筛法求出$2$~$\sqrt{R}$之间所有的质数，对于每个质数p，把$[L,R]$中能被p整除的数标记，即标记$i*p\left(\Big\lceil\dfrac{L}{P}\Big\rceil\le\Big\lceil\dfrac{R}{P}\Big\rceil\right)$为合数。
最终所有还没有被标记的数就是$\left[L,R\right]$中的质数。对相邻质数两两比较，找出差最大的即可。
时间复杂度为$O\left(\sum_{质数p\le\sqrt{R}}\frac{R-L}{p}\right)=O\left(\sqrt{R}loglog\sqrt{R}+(R-L)loglogR\right)$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN = 46345;
typedef long long ll;
int p[MAXN],cnt,l,r,m;
bool v[1000001];
int b[1000001];

void prime() {
	memset(v, 1, sizeof(v));
	for (int i = 2; i <= MAXN; i++)
		if (v[i]){
			p[++cnt] = i;
			for (int j = 2; j <= 46340 / i; j++) v[i*j] = false;
		}
}

int main() {
	prime();
	while (cin >> l >> r) {
		memset(v, 1, sizeof(v));
		if (l == 1) v[0] = false;
		for (ll i = 1; i <= cnt; i++)
			for (ll j = l / p[i]; j <= r / p[i]; j++) {
				if (p[i] * j - l < 0)continue;//这里不加，poj过不了
				if (j > 1) v[p[i] * j - l] = false;
			}
		m = 0;
		for (ll i = l; i <= r; i++){//这里一定要开ll的i，要不然溢出了就会死循环
			if (v[i - l]) b[++m] = i;
		}
		ll t1 = 2147483647; ll t2 = 0;
		ll x1, x2, y1, y2;
		for (ll i = 1; i<m; i++){
			ll cha = b[i + 1] - b[i];
			if (cha<t1) { t1 = cha; x1 = b[i]; y1 = b[i + 1]; }
			if (cha>t2) { t2 = cha; x2 = b[i]; y2 = b[i + 1]; }
		}
		if (!t2) cout << "There are no adjacent primes.\n";
		else cout << x1 << ',' << y1 << " are closest, " << x2 << ',' << y2 << " are most distant.\n";
	}
	return 0;
}